C1. Magnitude (Easy Version)

给你一个长度为 n 的数组 a 。从 c=0 开始。然后,对从 1n 的每个 i (按递增顺序)做以下***中的一个:

设上述步骤后 c 的最大终值等于 k 。求出 k

官方题解:

我们只需要选择一次 2 选项。为什么?假设我们不止一次选择了 2 ,那么考虑一下最后两次的选择。当 c+ai 为负数时,这两次都必须发生,否则就没有理由选择 2 而不是 1 。因此,如果我们在第一次操作中选择了 1 而不是 2 ,这将导致第二次操作前 c 的值减小。由于它是负值,这就增加了幅度,因此在第一次操作中选择 1 是更优的选择。

因为我们只需要使用一次选项 2 ,所以我们可以蛮力使用该操作,并用前缀和计算 c 的最终值。

即在 前缀和最小的位置且那个位置小于 0 使用操作 2,如果多次使用了操作 2 会导致反而变小。

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), pre(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)pre[i] = pre[i - 1] + a[i];
    int ans = pre[n];
    for (int i = 1;i <= n;i++) {
        if (pre[i] < 0) {
            ans = max(ans, pre[n] - 2 * pre[i]);
        }
    }
    cout << ans << '\n';

}

fi,0/1 代表前 i 个能达到的最大值/最小值

只需要维护最大值和最小值即可。

当前的最大值要么就是前 i1 项的最大值加上 ai 得到,要么是前 i1 项的最小值加上 ai 取绝对值得到。

最小值则是前 i1 项的最小值加上 ai

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];

    vector<array<int, 2>> f(n + 1);
    for (int i = 1;i <= n;i++) {
        f[i][0] = max(abs(f[i - 1][1] + a[i]), abs(f[i - 1][0] + a[i]));
        f[i][1] = f[i - 1][1] + a[i];
    }
    cout << max(f[n][1], f[n][0]) << '\n';
}